/**
////给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 
//// 
////
//// 示例 1 ： 
////
//// 
////输入：num = "1432219", k = 3
////输出："1219"
////解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
//// 
////
//// 示例 2 ： 
////
//// 
////输入：num = "10200", k = 1
////输出："200"
////解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
//// 
////
//// 示例 3 ： 
////
//// 
////输入：num = "10", k = 2
////输出："0"
////解释：从原数字移除所有的数字，剩余为空就是 0 。
//// 
////
//// 
////
//// 提示： 
////
//// 
//// 1 <= k <= num.length <= 10⁵ 
//// num 仅由若干位数字（0 - 9）组成 
//// 除了 0 本身之外，num 不含任何前导零 
//// 
//// Related Topics 栈 贪心 字符串 单调栈 👍 733 👎 0
//

*/

package com.xixi.basicAlgroithms.greedy;

import java.util.Stack;

public class ID00402RemoveKDigits {
public static void main(String[] args) {

    Solution solution = new ID00402RemoveKDigits().new Solution();
    System.out.println(solution.removeKdigits("1432219",3));
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public Stack<Character> numStack;

    public String removeKdigits(String num, int k) {

        char[] numChars = num.toCharArray();
        int numLength = numChars.length;
        numStack = new Stack<>();
        int newLength = numLength - k;
        char[] newNum = new char[newLength];
        if(numLength <= k) return "0";

        //每删掉1位相当于除10


        int cuttedIndex = 0; //删除的位数


        //删除的位数必须小于k

        //两种情况
        //1. 扫描之后没删到K个数 newNumIndex < (numChars.length - k)
        //2. 还没扫描到尾巴就删到K个数了 cuttedIndex < k 防止

        //先压栈，记录已经删除的位数cuttedIndex
        numStack.push(numChars[0]);
        for(int i = 1; i < numLength ; ++i ){
            //当前元素是低位，栈顶元素是高位
            //如果当前元素小于栈顶元素，就弹出，并把当前元素压栈
            if(numChars[i] < numStack.peek() &&
                cuttedIndex < k //删除位数必须小于k
            ){
                while(!numStack.isEmpty() && numChars[i] < numStack.peek() && cuttedIndex < k ){ //只要没删够位数，并且栈顶高位大于当前低位
                    numStack.pop();
                    ++cuttedIndex; //删除位数增加
                }
                numStack.push(numChars[i]);

            }else{
                numStack.push(numChars[i]);
            }

        }
        //循环结束后，可能没删够数目,从后往前删，删到够数为止
        while(cuttedIndex < k){
            numStack.pop();
            ++cuttedIndex; //删除位数增加
        }
        //返回值的索引
        int newNumIndex = newLength - 1;
        while(newNumIndex >= 0 && !numStack.isEmpty()){
            newNum[newNumIndex] = numStack.pop();//填充数字
            --newNumIndex;
        }

        //去掉前导0
        int preIndex = 0;
        while(newNum[preIndex] == '0' && preIndex < newLength - 1){
            ++preIndex;
        }
        String result = new String(newNum).substring(preIndex);

        return result;


    }
}
//leetcode submit region end(Prohibit modification and deletion)




}